Cryptography involves the transmission of an encrypted message from one party to another. The message is encrypted using a mathematical function known as a cryptographic algorithm, which for security reasons allows for a large number of initial settings, the selection being determined by a cryptographic key. The cryptographic algorithm must be complex enough so that the encrypted message cannot be decrypted by an unintended party if the cryptographic algorithm is known but the key is not. If both the algorithm and the key are known by an unintended party then the unintended party may decrypt the encrypted message. Typically, the algorithm is known to all, but the key is known only by the intended parties. Therefore, the security of the encrypted message lies in maintaining the secrecy of the key.
An unencrypted message (i.e., plaintext) is encrypted (i.e., converted to ciphertext) by a sender by using a cryptographic system to mathematically alter the plaintext using a cryptographic algorithm and a key. An intended receiver recovers the plaintext by mathematically altering the ciphertext using a crypto-algorithm and a key in a manner that is the mathematical inverse of the mathematical function performed by the sender.
Modern cryptographic systems fall into two categories: symmetric-key crypto-systems and public-key crypto-systems. A symmetric-key crypto-system is one in which the encryption key and the decryption key are computable from one another (the keys are often the same), so that one secret must be agreed upon off-line by the users before secure communication can take place. A public-key crypto-system is one in which the decryption key cannot feasibly be computed from the encryption key, so that the encryption key can be made public without compromising the security of the system. Having two different keys for encryption and decryption, where knowledge of the encryption key does not betray the decryption key, solves a problem that exists in a symmetric-key system (i.e., key distribution) and enables the parties to perform additional functions (i.e., electronic key exchange, non-repudiation, and message authentication).
Cryptography used to be practiced only by governments that had cryptographic expertise and the money to afford such equipment. However, it is envisioned that reasonably priced cryptographic equipment will become commercially available to the general public. Eventually, all communications may be encrypted. This is good for preventing espionage from being performed on our citizens by foreign powers, but it may also prevent our own law enforcement professionals from conducting authorized wiretaps. Key escrow, which is described below, is being proposed as a solution to the law enforcement problem. Key escrow also has uses outside of law enforcement (e.g., corporate monitoring of customer hotlines for quality control).
The term "key escrow" is used to refer to a scheme of allowing an authorized third party access to the key used to encrypt communications between a first party and a second party. That which is escrowed may be the key itself, or a more primitive element of the system from which the session key (i.e., the key used to encrypt the communications between the first party and the second party in a particular communication session) can be computed. Most key escrow schemes involve procedures that place them among one or more of the following three varieties.
The first variety of key escrow is one where the session key, essentially unaltered, or a short term secret from which the session key is produced (during the validity period of the short term secret), is given to one or more trustees. If multiple trustees are used, each trustee may hold the entire session key or a portion thereof. A third party wanting access to the session key would go to the trustee or trustees and ask for the session key or the portions thereof. Some sort of authorization process (e.g., corporate approval, law enforcement warrant, etc.) is required to prevent access to the session key by an unauthorized third party.
The second variety of key escrow requires, for each secure communication, the transmission, either by the sender or by both parties, of additional data not necessary for the first and second parties. The additional data, sometimes in the form of ancillary messages, is constructed in a way that allows an authorized third party to recover the session key either directly or with the authorized cooperation of the one or more trustees. Two terms are presently being used to describe additional data transmitted by the sender: law enforcement access field (LEAF) and data recovery field (DRF). The LEAF, or DRF, is not needed by either the first or second party for secure communication and, as such, is per-message overhead. Furthermore, the additional data need not be readable by the communicating parties. Therefore, misuse of the system by an intentional corruption of the LEAF or the DRF may be undetectable by an honest user. A requirement to send extra messages for the purpose of enabling authorized third party access is generally considered more of a burden than increasing the length of a message already intended to be sent by a user (as in appending a LEAF). Furthermore, the exchange of preliminary messages (often referred to as a handshake) prior to communication may preclude a system's use in some very important applications (such as e-mail) in which both users need not be concurrently on line to communicate.
The third variety of key escrow is one where a long term secret, from which per message session keys are derived, is given to one or more trustees. This variety often involves incorporating key escrow into the enrollment process of the system, in which session keys themselves are not stored, but rather long term data used in the production of session keys is escrowed. As the session keys subsequently computed depend only on the escrowed data and known quantities (e.g., the time of communication), there need be no per message overhead to enable authorized third party access to session keys. The present invention is of this third variety.
Dorothy E. Denning and Dennis K. Branstad wrote a survey of existing key escrow schemes in a paper entitled "A Taxonomy for Key Escrow Encryption Systems," published in Communications of the ACM, in March, 1996. Ms. Denning updated this survey in a paper entitled "Description of Key Escrow Systems," Version of May 1, 1996, available on the INTERNET (at http://guru.cosc.georgetown.edu/.about.denning/crypto/Appendix.html). The updated survey is a compilation of descriptions, apparently submitted by the creators, of existing key escrow schemes. From the brief descriptions given in this paper, it appears that most of the key escrow schemes contained therein are of either the first variety (i.e., escrow the unaltered session key or the short term secrets from which session key is produced with one or more trustees) or of the second variety (i.e., append a LEAF or DRF to the encrypted communication or require some form of handshake for the purpose of enabling authorized third party access). The key escrow scheme described by Arjen K. Lenstra, Peter Winkler, and Yacov Yacobi, in a paper entitled "A Key Escrow System with Warrant Bounds," Advances in Cryptology--Crypto '95 Proceedings, Springer-Verlag, 1995, pp 197-207, is significantly different from the present invention but may come the closest to the present invention of any published key escrow scheme because it is a key escrow scheme not only of the second variety but also of the third variety.
In the method of Lenstra et al., two users (e.g., User A and User B) who wish to communicate securely each generate, or are given, a Diffie-Hellman public key pair (based on a large prime integer p and a positive integer g) consisting of a public encryption key P.sub.i and a secret encryption key S.sub.i, where P.sub.i and S.sub.i are related by P.sub.i =gS.sub.i mod p, where "" denotes exponentiation. That is, User A possesses P.sub.A and S.sub.A while User B possesses P.sub.B and S.sub.B. The secret encryption keys of the users are escrowed unaltered with one or more trustees. Each user publishes its public encryption key in a directory that is available to the other user.
Next, User A generates the session key k(A,B,d) that will be used to encrypt messages between the two users. The session key is generated using the secret encryption key S.sub.A of User A, the public encryption key P.sub.B of User B, and the date of the intended communication. More precisely, the session key is generated using a one-way hash function h to hash the date into a number formed by raising P.sub.B to S.sub.A in a manner similar to the Diffie-Hellman key-exchange method (i.e., U.S. Pat. No. 4,200,770). U.S. Pat. No. 4,200,770 is hereby incorporated by reference into the specification of the present invention. That is, User A generates k(A,B,d)=h(P.sub.B S.sub.A,d). User B generates the session key in a slightly different, but mathematically equivalent, manner, i.e., k(B,A,d)=h(P.sub.A S.sub.B,d)=k(A,B,d).
Next, Lenstra et al. requires each user to generate a key encryption key for encrypting the session key. The encrypted session key is then used as a LEAF. The key encryption key generated by each user is not known by the other user. User A generates S(A,B,d)=h(h(S.sub.A,d),P.sub.B). User B generates S(B,A,d)=h(h(S.sub.B,d),P.sub.A). The key encryption key of each user is tied to the other user through the public encryption key of the other user.
Next, Lenstra et al. requires each user to encrypt its session key with its key encryption key and transmit the result (i.e., the LEAF). The LEAF, which the other user cannot decrypt, is transmitted solely for the benefit of an authorized third party.
Next, Lenstra et al. requires an authorized third party, who intercepts an encrypted communication between User A and User B, to present some form of authorization and the date the encrypted communication was sent to the one or more trustees in order to get one of three datums.
If the third party is authorized to decrypt all messages between User A and User B on a given date regardless of the direction of the communication (i.e., User A to User B or vice versa) then the one or more trustees will give the third party the key encryption key S(A,B,d) of one of the users. For example, if the third party is interested in User A's communications then User A's key encryption key S(A,B,d) will be given to the third party. This datum enables the third party to decrypt the LEAF transmitted for the third party's benefit (i.e., the session key k(A,B,d) encrypted with the key encryption key S(A,B,d)). After recovering k(A,B,d), the third party may decrypt all communications for which it is the session key (presumably on the date k(A,B,d) was created) between the users (irrespective of the direction of the communication; User A to User B or vice versa). This is the most restrictive access granted by Lenstra et al. Technically, the datum enables the third party to decrypt messages any time the session key is used by the users, but if the users use the session key only on the date it is created then the datum given to the third party will only enable the third party to decrypt messages between the two users on that date.
If the third party is authorized to decrypt all messages sent or received by a particular user (e.g., User A) to any other second party (e.g., User C as well as User B) on a particular date then the third party is given the hash of the secret encryption key of the user and the date in question (e.g., h(S.sub.A,d)). This datum is used in producing any key encryption key generated (e.g., S(A,B,d), S(A,C,d), etc.) by the user on the date in question for any other user (e.g., User B, User C, etc.). Knowing this datum, the hash function, and the public encryption key of the user, the third party may reconstruct the user's key encryption key.
If a third party is authorized to decrypt all messages sent by a particular user on any day and the LEAF is corrupted or absent (e.g., the user tries to deny access by an authorized third party), the third party is given the secret encryption key of that particular user (e.g., S.sub.A for User A). With this, the third party may create all datums required to decrypt the messages received by or sent from the user. This situation remains in effect until the user gets a new public key.
The significant differences between the key escrow scheme of Lenstra et al. and the present invention are that
(1) the present invention is not of the second variety, whereas Lenstra et al. is of the second variety, that is, the present invention does not require per message overhead for authorized third party access (a LEAF or the consequent generation of a key encryption key) as in the key escrow scheme of Lenstra, et al.;
(2) the present invention may restrict access to messages based on the direction of the message (i.e., who sent the message to whom) whereas Lenstra et al. does not;
(3) the present invention includes multiple policy-definable access restriction levels whereas Lenstra et al. only uses one (i.e., date);
(4) in the present invention, if one of a pair of users is honest, cooperating with the protocol set forth in the present invention, then secure communication can only take place if the other is honest: secure communication thus guarantees each user that the other is not circumventing authorized third party access;
(5) the present invention never reveals the secret encryption key of a user to the authorized third party whereas Lenstra et al. may.
U.S. Pat. No. 5,535,276, entitled "YAKSHA, AN IMPROVED SYSTEM AND METHOD FOR SECURING COMMUNICATIONS USING SPLIT PRIVATE KEY ASYMMETRIC CRYPTOGRAPHY," is a patent on the key escrow scheme described in the Denning papers listed above. The key escrow scheme of U.S. Pat. No. 5,535,276 is of the first variety listed above. The present invention is not of the first variety listed above. U.S. Pat. No. 5,535,276 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,557,765, entitled "SYSTEM AND METHOD FOR DATA RECOVERY," discloses a key escrow scheme of the second variety (i.e., one that includes a data recovery field). U.S. Pat. No. 5,557,765 is a patent on a key escrow scheme attributed to Trusted Information Systems, Inc. in the Denning papers listed above. The present invention is not of the second variety key escrow scheme listed above. U.S. Pat. No. 5,557,765 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. Nos. 5,276,737 and 5,315,658, both entitled "FAIR CRYPTOSYSTEMS AND METHODS OF USE," disclose three key escrow schemes. One, in which secret encryption keys are escrowed, allows authorized third parties to reconstruct a user's secret encryption key, allowing access to all messages sent to or from the user for all time. In contrast, the present invention restricts access in both time and direction of communication, and furthermore never reveals secret encryption keys. A second one achieves time-boundedness of access to authorized third parties by requiring users to escrow multiple secret encryption keys (e.g., one each month), so that a secret encryption key reconstructed by an authorized third party eventually expires. As such, this system is of the first variety, whereas the present invention is not of the first variety. A third one achieves time boundedness of access to authorized third parties but requires three messages to be passed between the users. Since the last two are unnecessary for communication, and are sent only to enable authorized third party access, this system is of the second variety whereas the present invention is not of the second variety. U.S. Pat. Nos. 5,276,737 and 5,315,658 are hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,436,972, entitled "METHOD FOR PREVENTING INADVERTENT BETRAYAL BY A TRUSTEE OF ESCROWED DIGITAL SECRETS," is rather a data recovery scheme than a key escrow scheme used for secure communication. U.S. Pat. No. 5,436,972 adds to the secret information that is provided to one or more trustees additional identification information, whereas the present invention accomplishes data recovery with no additional overhead. Furthermore, in U.S. Pat. No. 5,436,972, the escrow agent and data recovery center are one and the same, whereas in the present invention they are not. U.S. Pat. No. 5,436,972 is hereby incorporated by reference into the specification of the present invention.
U.S. Pat. No. 5,557,678, entitled "SYSTEM AND METHOD FOR CENTRALIZED SESSION KEY DISTRIBUTION, PRIVACY ENHANCED MESSAGING AND INFORMATION DISTRIBUTION USING A SPLIT PRIVATE KEY PUBLIC CRYPTOSYSTEM," discloses a variant of the first variety of key escrow scheme listed above. That is, U.S. Pat. No. 5,557,678 distributes an encrypted version of the session key to authorized third parties. The present invention is not of the first variety key escrow scheme listed above. U.S. Pat. No. 5,557,678 is hereby incorporated by reference into the specification of the present invention.